package com.structure.algorithm;

/**
 * @Author Tanyu
 * @Date 2020/6/1 14:14
 * @Description 无重复字符的最长子串
 * @Version 1.0
 */
public class LengthOfLongestSubstring {

  public static void main(String[] args) {

    String s = "abcabcbb";
    int i = lengthOfLongestSubstring(s);
    System.out.println(i);
    System.out.println(lengthOfLongestSubstring1(s));
  }

  public static int lengthOfLongestSubstring(String str) {
    int i = 0;
    int flag = 0;
    int length = 0;
    int result = 0;
    while (i < str.length()) {
      int pos = str.indexOf(str.charAt(i), flag);
      if (pos < i) {
        if (length > result) {
          result = length;
        }
        if (result >= str.length() - pos - 1) {
          return result;
        }
        length = i - pos - 1;
        flag = pos + 1;
      }
      length++;
      i++;
    }
    return length;
  }


  public static int lengthOfLongestSubstring1(String str) {
    int maxSize = 0;
    int[] dict = new int[256]; //记录ASCII 码字符出现的位置，以字符作为下标
    int base = 0;
    int key = 0;
    int i = 0;
    while (key < str.length()) {
      i = str.charAt(key);
      if (dict[i] > base) {
        base = dict[i];
      }
      dict[i] = key + 1; //以1作为起始位置，下标加1
      maxSize = (maxSize > key - base + 1) ? maxSize : key - base + 1;
      key++;
    }
    return maxSize;
  }

}
